package shu;

import java.util.Arrays;
import java.util.Random;

public class Maxheap<T extends Comparable<T>> {
    /*
     *构建最大堆
     * 注意：根节点对应的索引为0
     * */

    private T[] data;
    private int size;

    public Maxheap() {
        this.data = (T[]) new Comparable[200];
        this.size = 0;
    }

    public Maxheap(T[] arr) {
        this.data = Arrays.copyOf(arr, arr.length);
        this.size = arr.length;

    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    //获得堆的长度
    public int getsize() {
        return this.size;
    }

    //获取左孩子索引
    private int getleftchildindex(int index) {
        if (index < 0) {
            throw new IllegalArgumentException("index is error");
        }
        return 2 * index + 1;
    }

    //获取父节点索引
    private int getparentindex(int index) {
        if (index < 0) {
            throw new IllegalArgumentException("index is error");
        } else if (index == 0) {
            return -1;
        } else {
            return (index - 1) / 2;
        }
    }

    //添加操作
    public void add(T ele) {
        //1.保存数据
        data[this.size] = ele;
        //2.更新操作
        size += 1;
        //3.浮动操作
        //floatup(size - 1);
        floatup1(ele);
    }

    private void floatup1(T ele) {
        //1、获取父亲节点的索引
        int curindex = this.size - 1;
        int parentindex = getparentindex(curindex);
        // 2、比较优先级，如果比父亲节点的优先级高，就交换
        while (curindex > 0 && ele.compareTo(data[parentindex]) > 0) {
            data[curindex] = data[parentindex];
            curindex = parentindex;
            parentindex = getparentindex(curindex);
        }
        data[curindex] = ele;
    }

    //浮动操作
    private void floatup(int i) {
        //获取父节点的索引
        int parentindex = getparentindex(i);
        // 2、比较优先级，如果比父亲节点的优先级高，就交换
        while (parentindex >= 0) {
            if (data[i].compareTo(data[parentindex]) > 0) {
                swap(this.data, i, parentindex);
                i = parentindex;
                parentindex = getparentindex(i);
            } else {
                break;
            }
        }
    }

    private void swap(T[] arr, int curindex, int changeindex) {
        T temp = arr[curindex];
        arr[curindex] = arr[changeindex];
        arr[changeindex] = temp;

    }



    //删除操作
    private  T getPriorityFirst(){
        if(isEmpty()){
            throw  new IllegalArgumentException("堆为空");
        }
        //1.保存跟元素
T result=this.data[0];
        //2.用最后一个元素替换跟元素
this.data[0]=this.data[this.size-1];
        //3.更新size
        this.size-=1;
        //swim操作
        swim1();
        return result;
    }

    //下沉操作
    private void swim() {
        if (isEmpty()){
            return;
        }
        int curindex=0;
        int leftindex=getleftchildindex(curindex);
        int changeindex=leftindex;//保存左右孩子优先级高的索引
        //有左孩子的条件leftindex<this.size

        while (leftindex<this.size) {
            if (leftindex + 1 < this.size && data[leftindex].compareTo(data[leftindex + 1]) < 0) {
                changeindex = leftindex + 1;
            }
            if(data[curindex].compareTo(data[changeindex])>0){
                return;
            }
            swap(this.data, curindex, changeindex);
            curindex = changeindex;
            leftindex = getleftchildindex(curindex);
            changeindex = leftindex;
        }
    }


    private void swim1() {
        if (isEmpty()){
            return;
        }
        T rootele=this.data[0];
        int curindex=0;
        int leftindex=getleftchildindex(curindex);
        int changeindex=leftindex;//保存左右孩子优先级高的索引
        //有左孩子的条件leftindex<this.size

        while (leftindex<this.size) {
            if (leftindex + 1 < this.size && data[leftindex].compareTo(data[leftindex + 1]) < 0) {
                changeindex = leftindex + 1;
            }
            if(rootele.compareTo(data[changeindex])>0){
                return;
            }
            data[curindex]=data[changeindex];
            curindex = changeindex;
            leftindex = getleftchildindex(curindex);
            changeindex = leftindex;
        }
        data[curindex]=rootele;
    }


    //replace操作：取出优先级最高的元素，放入一个新元素（让新元素替换跟元素）

    public void replace(T newele){
        this.data[0]=newele;
        swim1();
    }

    //heapify操作:将任意数组整理成堆
    //方式一：一次添加
    public void heapify() {
        if (this.data == null || this.data.length == 0) {
            return;
        }
        int lastEleParentIndex = (this.data.length - 1 - 1) / 2;
        for (; lastEleParentIndex >= 0; lastEleParentIndex--) {
            heapifyswim(this.data, lastEleParentIndex, this.data.length);
        }
    }

    private void heapifyswim(T[] arr, int lastEleParentIndex, int length) {
        int curIndex = lastEleParentIndex;
        int leftIndex = getleftchildindex(curIndex);
        int changeIndex = leftIndex;
        while (leftIndex < length) {
            if (leftIndex + 1 < length && arr[leftIndex].compareTo(arr[leftIndex + 1]) < 0) {
                changeIndex = leftIndex + 1;
            }
            if (arr[curIndex].compareTo(arr[changeIndex]) > 0) {
                break;
            }
            swap(arr, curIndex, changeIndex);
            curIndex = changeIndex;
            leftIndex = getleftchildindex(curIndex);
            changeIndex = leftIndex;
        }
    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        int i = 0;
        while (i < size) {
            sb.append(this.data[i]);
            if (i != size - 1) {
                sb.append(",");
            }
            i++;
        }
        sb.append("]");
        return sb.toString();
    }
//堆排序
    public void sort(T[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        // 构建堆
        Arrays.stream(arr).forEach(item -> this.add(item));
        // 依次删除根节点
        int index = 0;
        while (!isEmpty()) {
            arr[index++] = this.getPriorityFirst();
        }
    }


    public static void main(String[] args) {
       /* Random random = new Random();
        Maxheap<Integer> heap = new Maxheap<>();
        for (int i = 0; i < 7; i++) {
            heap.add(random.nextInt(60));
        }
        System.out.println(heap);
        heap.add(51);
        System.out.println(heap);

        //删除优先级最高的元素
        int max=heap.getPriorityFirst();
        System.out.println(max);
        System.out.println(heap);
        */

/*
        Random random = new Random();
        Integer[] arr = new Integer[12];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(50);
        }
        Maxheap<Integer> heap = new Maxheap<>(arr);
        System.out.println(heap);
        heap.heapify();
        System.out.println("------------heapify操作之后---------------");
        System.out.println(heap);*/



        Random random = new Random();
        Integer[] arr = new Integer[12];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(50);
        }
        Maxheap<Integer> heap = new Maxheap<>();
        heap.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}


